﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EightNum
{
    class EnAlgorithm
    {
        Form1 form1;

        //------------------------------------------------------------------
        public EnAlgorithm(Form1 a)
        {
            this.form1 = a;
        }

        //启发式搜索算法
        public void getFinPathQf()//寻找解路径，创建关键路径数组
        {
            this.initSerchQf();//搜索初始化

            int deep = 1;
            while (form1.finc == -1)
            {
                this.goNextDeepQf(deep);
                deep++;
            }

            if (form1.finc == 0)//本身就是目标状态且没有溢出
            {
                form1.fin[0] = new KeyArr(form1.templeQf[0].key);
            }

            if (!form1.isOverFlow)
            {
                try
                {
                    int tag = form1.finc;
                    for (int j = 1; tag != 0; j++)//fin[0]是目标状态
                    {
                        tag = form1.templeQf[tag].parent;//temple[0-n]存储的是当前状态到目标状态，fin【0-n】是目标状态到当前状态
                        form1.fin[j] = new KeyArr(form1.templeQf[tag].key);//捕获此异常，防止越界
                    }

                    for (int i = 0; i < form1.templeQf.Length - 1; i++)//求出fin后便可以释放temple内存了
                    {
                        if (form1.templeQf[i] != null)
                        {
                            form1.templeQf[i] = null;
                        }
                    }


                    int r = 0;
                    while (form1.fin[r] != null)
                    {
                        r++;
                    }
                    form1.finLength = r;
                }
                catch (Exception)
                {
                    form1.finc = -3;//越界类型
                    form1.isOverFlow = true;//标识溢出，结束操作
                }
            }

        }

        public void goNextDeepQf(int ndeep)//启发式扩展层
        {
            int minfun = -1;//记录一层中最小的评价函数
            try
            {
                int tcount1 = form1.tcount;//创建临时变量tcount1，访问当前已创建的现有的所有节点，而tcount会继续增加

                for (int i = 0; i <= tcount1; i++)//这里先搜索一遍，是牺牲时间，换取空间的方式，可以不要该循环，换取时间的缩短
                {
                    if (form1.templeQf[i].deepth == ndeep)//扫描该层的所有节点
                    {
                        if (Utilities.checkUp(form1.templeQf[i].key, form1.tkey))//如果该节点是目标节点，则返回
                        {
                            form1.finc = i;
                            return;
                        }

                        if (minfun == -1)//初始化最小的评价函数
                        {
                            minfun = form1.templeQf[i].fun;
                        }

                        if (form1.templeQf[i].fun <= minfun)
                        {
                            minfun = form1.templeQf[i].fun;
                        }

                    }
                }

                for (int i = 0; i <= tcount1; i++)//这个循环就是用来扩展节点的了
                {
                    if (form1.templeQf[i].deepth == ndeep && form1.templeQf[i].fun == minfun)//必须是该层的节点且评价函数是最小的
                    {
                        if (Utilities.checkUp(form1.templeQf[i].key, form1.tkey))//如果该节点是目标节点，则返回
                        {
                            form1.finc = i;
                            return;
                        }
                        //开始拓展下一层节点
                        if (form1.templeQf[i].istoUp)
                        {
                            byte[,] tr = Utilities.getMoveUp(form1.templeQf[i].key);
                            form1.tcount++;
                            form1.templeQf[form1.tcount] = new Qfnode(1, i, tr, ndeep + 1, form1.tkey);
                        }

                        if (form1.templeQf[i].istoDown)
                        {
                            byte[,] tr = Utilities.getMoveDown(form1.templeQf[i].key);
                            form1.tcount++;
                            form1.templeQf[form1.tcount] = new Qfnode(2, i, tr, ndeep + 1, form1.tkey);
                        }

                        if (form1.templeQf[i].istoLeft)
                        {
                            byte[,] tr = Utilities.getMoveLeft(form1.templeQf[i].key);
                            form1.tcount++;
                            form1.templeQf[form1.tcount] = new Qfnode(3, i, tr, ndeep + 1, form1.tkey);
                        }

                        if (form1.templeQf[i].istoRight)
                        {
                            byte[,] tr = Utilities.getMoveRight(form1.templeQf[i].key);
                            form1.tcount++;
                            form1.templeQf[form1.tcount] = new Qfnode(4, i, tr, ndeep + 1, form1.tkey);
                        }
                    }
                }
            }
            catch (Exception)
            {
                form1.finc = -2;//为了终止循环,-2标记是templeQf溢出
                form1.isOverFlow = true;//标识溢出，结束操作

                for (int i = 0; i < form1.templeQf.Length - 1; i++)//释放temple内存
                {
                    if (form1.templeQf[i] != null)
                    {
                        form1.templeQf[i] = null;
                    }
                }
            }
        }

        public void initSerchQf()//搜索初始化函数
        {
            //需要初始化两个数组

            for (int j = 0; j <= form1.fin.Length - 1; j++)
            {
                if (form1.fin[j] != null)
                {
                    form1.fin[j] = null;
                }
            }

            form1.isOverFlow = false;
            form1.tcount = 0;//计数节点个数！
            form1.finc = -1;//目标状态的编号,记录最后一个目标所在的数组下标！
            form1.finLength = 0;//关键路径长度

            form1.tcount = 0;//当前数组位置
            form1.templeQf[form1.tcount] = new Qfnode(-1, -1, form1.pkey, 1, form1.tkey);//初始化当前状态
            form1.fin[0] = new KeyArr(form1.tkey);//fin[0]是目标状态
        }

        //结束

        public void getFinPathGd()//寻找解路径，创建关键路径数组
        {
            this.initSerch();//搜索初始化

            int deep = 1;
            while (form1.finc == -1)
            {
                this.goNextDeep(deep, form1.tkey);
                deep++;
            }

            if (form1.finc == 0)//本身就是目标状态
            {
                form1.fin[0] = new KeyArr(form1.temple[0].key);
            }

            if (!form1.isOverFlow)
            {
                try
                {
                    int tag = form1.finc;
                    for (int j = 1; tag != 0; j++)//fin[0]是目标状态
                    {
                        tag = form1.temple[tag].parent;//temple[0-n]存储的是当前状态到目标状态，fin【0-n】是目标状态到当前状态
                        form1.fin[j] = new KeyArr(form1.temple[tag].key);
                    }

                    for (int i = 0; i < form1.temple.Length - 1; i++)//求出fin后便可以释放temple内存了
                    {
                        if (form1.temple[i] != null)
                        {
                            form1.temple[i] = null;
                        }
                    }

                    //finLength = fin.Length;
                    int r = 0;
                    while (form1.fin[r] != null)
                    {
                        r++;
                    }
                    form1.finLength = r;
                    //fin[r - 1] = new KeyArr(this.nkey);
                }
                catch (Exception)
                {
                    form1.finc = -3;//越界类型
                    form1.isOverFlow = true;//标识溢出，结束操作
                }
            }

        }

        public void goNextDeep(int ndeep, byte[,] tkey)//扩展层
        {
            try
            {
                int tcount1 = form1.tcount;//创建临时变量tcount1，访问当前已创建的现有的所有节点，而tcount会继续增加

                for (int i = 0; i <= tcount1; i++)//这里先搜索一遍，是牺牲时间，换取空间的方式，可以不要该循环，换取时间的缩短
                {
                    if (form1.temple[i].storey == ndeep)//扫描该层的所有节点
                    {
                        if (Utilities.checkUp(form1.temple[i].key, form1.tkey))//如果该节点是目标节点，则返回
                        {
                            form1.finc = i;
                            return;
                        }
                    }
                }

                for (int i = 0; i <= tcount1; i++)//这个循环就是用来扩展节点的了
                {
                    if (form1.temple[i].storey == ndeep)
                    {
                        if (Utilities.checkUp(form1.temple[i].key, form1.tkey))//如果该节点是目标节点，则返回
                        {
                            form1.finc = i;
                            return;
                        }
                        //开始拓展下一层节点
                        if (form1.temple[i].istoUp)
                        {
                            byte[,] tr = Utilities.getMoveUp(form1.temple[i].key);
                            form1.tcount++;
                            form1.temple[form1.tcount] = new Enode(1, i, tr, ndeep + 1);
                        }

                        if (form1.temple[i].istoDown)
                        {
                            byte[,] tr = Utilities.getMoveDown(form1.temple[i].key);
                            form1.tcount++;
                            form1.temple[form1.tcount] = new Enode(2, i, tr, ndeep + 1);
                        }

                        if (form1.temple[i].istoLeft)
                        {
                            byte[,] tr = Utilities.getMoveLeft(form1.temple[i].key);
                            form1.tcount++;
                            form1.temple[form1.tcount] = new Enode(3, i, tr, ndeep + 1);
                        }

                        if (form1.temple[i].istoRight)
                        {
                            byte[,] tr = Utilities.getMoveRight(form1.temple[i].key);
                            form1.tcount++;
                            form1.temple[form1.tcount] = new Enode(4, i, tr, ndeep + 1);
                        }
                    }
                }
            }
            catch (Exception)
            {
                form1.finc = -2;//为了终止循环
                form1.isOverFlow = true;//标识溢出，结束操作

                for (int i = 0; i < form1.temple.Length - 1; i++)//释放temple内存
                {
                    if (form1.temple[i] != null)
                    {
                        form1.temple[i] = null;
                    }
                }
            }
        }

        public void initSerch()//搜索初始化函数
        {
            //需要初始化两个数组

            for (int j = 0; j <= form1.fin.Length - 1; j++)
            {
                if (form1.fin[j] != null)
                {
                    form1.fin[j] = null;
                }
            }

            form1.isOverFlow = false;
            form1.tcount = 0;//计数节点个数！
            form1.finc = -1;//目标状态的编号,记录最后一个目标所在的数组下标！-1是默认状态
            form1.finLength = 0;//关键路径长度

            form1.tcount = 0;//当前数组位置
            form1.temple[form1.tcount] = new Enode(-1, -1, form1.pkey, 1);
            form1.fin[0] = new KeyArr(form1.tkey);//fin[0]是目标状态
        }

    }
}
